The Internet enables access to a wide variety of resources, such as video or audio files, web pages for particular subjects, book articles, or news articles. A search system can identify resources in response to a user query that includes one or more search terms or phrases. The search system ranks the resources based on their relevance to the query and importance and provides search results that link to the identified resources, and orders the search results according to the rank.
A search system uses a search operation to identify resources that are responsive to the query. The search operation takes into account features of the resources and the query, and perhaps other information, when generating search scores for the resources. Typically the search operation implements a robust search algorithm that performs well over a wide variety of resources. However, sometimes it is desirable to model outcomes with respect to a query and a resource. For example, models can be machine learned to predict outcomes such as a likelihood of an installation of an application given a query; a likelihood of a purchase given a query; and so on. Often these models emit scoring rules in the form of tuples that define a feature for a query-resource pair and a constituent value. While these tuples may express rules that are very accurate for observed data, the rules may not readily apply to data not yet observed. Examples of data not yet observed are very long tail queries (or new queries), newly published resources, and any query resource pair that has not yet been observed.